package BinaryTree;

import java.util.*;

/**
 * Creat with IntelliJ IDEA
 * Description:二叉树的实现
 * User:WZW
 * Date:2022-02-08
 * Time:8:53
 */
class TreeNode{
    char val;
    TreeNode leftChild;
    TreeNode rightChild;

    public TreeNode(char val){
        this.val = val;
    }
}

public class BinaryTree {

    public TreeNode root;
    /*
    穷举的方式创建一颗二叉树
     */

    public TreeNode BinaryTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.leftChild = B;
        A.rightChild = C;
        B.leftChild = D;
        B.rightChild = E;
        E.rightChild = H;
        C.leftChild = F;
        C.rightChild = G;

        root = A;
        return root;
    }

    /*
    前序遍历
     */
    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.leftChild);
        preOrder(root.rightChild);
    }

    public List<Character> preorderTraversal2(TreeNode root){
        List<Character> list = new ArrayList<>();
        pre(root,list);
        return list;
    }
    public void pre(TreeNode root, List<Character> list){
        if (root != null){
            list.add(root.val);
            pre(root.leftChild, list);
            pre(root.rightChild, list);
        }
    }

    /*
    子问题思路解决
     */
    public List<Character> preorderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        list.add(root.val);
        List<Character> leftList = preorderTraversal(root.leftChild);
        list.addAll(leftList);
        List<Character> rightList = preorderTraversal(root.rightChild);
        list.addAll(rightList);
        return list;
    }

    /*
    中序遍历
     */
    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.leftChild);
        System.out.print(root.val+" ");
        inOrder(root.rightChild);
    }

    public List<Character> inorderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        List<Character> leftList = inorderTraversal(root.leftChild);
        list.addAll(leftList);
        list.add(root.val);
        List<Character> rightList = inorderTraversal(root.rightChild);
        list.addAll(rightList);
        return list;
    }

    /*
    后序遍历
     */
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        postOrder(root.leftChild);
        postOrder(root.rightChild);
        System.out.print(root.val+" ");
    }

    public List<Character> postorderTraversal(TreeNode root){
        List<Character> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        List<Character> leftList = postorderTraversal(root.leftChild);
        list.addAll(leftList);
        List<Character> rightList = postorderTraversal(root.rightChild);
        list.addAll(rightList);
        list.add(root.val);
        return list;
    }

    // 获取树中节点的个数
    //遍历思路：
    int count = 0;
    public int size2(TreeNode root){
        if (root == null){
            return 0;
        }
        count++;
        size2(root.leftChild);
        size2(root.rightChild);
        return count;
    }

    /*
    获取树中节点的个数
    子问题思路：
     */
    public int size(TreeNode root){
        if (root != null){
            return 1+size(root.leftChild)+size(root.rightChild);
        }
        return 0;
    }

    // 获取叶子节点的个数
    //遍历思路：
    int leafCount = 0;
    public int getLeafNodeCount2(TreeNode root){
        if (root == null){
            return 0;
        }
        if (root.leftChild == null && root.rightChild == null){
            leafCount++;
        }
        getLeafNodeCount2(root.leftChild);
        getLeafNodeCount2(root.rightChild);
        return leafCount;
    }
    /*
    子问题思路
     */
    public int getLeafNodeCount(TreeNode root){
        if (root == null){
            return 0;
        }
        if (root.leftChild == null && root.rightChild == null){
            return 1;
        }
        return getLeafNodeCount(root.leftChild) + getLeafNodeCount(root.rightChild);
    }

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root, int k){
        if (root == null || k <= 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.leftChild,k-1)+getKLevelNodeCount(root.rightChild,k-1);
    }

    /*
    获取二叉树的高度
     */
    public int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = getHeight(root.leftChild);
        int rightHeight = getHeight(root.rightChild);
        return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    }

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, char val){
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        TreeNode ret = find(root.leftChild,val);
        if (ret != null){
            return ret;
        }
        ret = find(root.rightChild,val);
        return ret;
    }

    /*
    判断一棵树是不是完全二叉树
     */
    public boolean isCompleteTree(TreeNode root){
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.leftChild);
                queue.offer(cur.rightChild);
            }
            else break;
        }
        while (!queue.isEmpty()){
            TreeNode top = queue.peek();
            if (top != null){
                return false;
            }
            queue.poll();
        }
        return true;
    }

    /*
    判断两棵树是否相同
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null){
            return true;
        }
        if(p==null || q==null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        if(isSameTree(p.leftChild,q.leftChild) == true){
            return isSameTree(p.rightChild,q.rightChild);
        }
        return false;
    }
    /*
    判断是否是子树
    */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==null)return false;
        if(isSameTree(root,subRoot)==true)return true;
        if(isSubtree(root.leftChild,subRoot)==true)return true;
        if(isSubtree(root.rightChild,subRoot)==true)return true;
        return false;
    }

    /*
    判断平衡二叉树
    时间复杂度：O(n)
     */
    public int height2(TreeNode root){
        if(root==null)return 0;
        int leftHeight = height2(root.leftChild);
        int rightHeight = height2(root.rightChild);

        if(leftHeight>=0 && rightHeight>=0 && Math.abs(leftHeight-rightHeight)<=1){
            return (Math.max(leftHeight,rightHeight)+1);
        }
        return -1;
    }

    public boolean isBalanced(TreeNode root) {
        return height2(root)>=0;
    }

    /*
    判断是否对称树
     */
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree==null && rightTree==null){
            return true;
        }
        if(leftTree==null || rightTree==null){
            return false;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.leftChild,rightTree.rightChild) && isSymmetricChild(leftTree.rightChild,rightTree.leftChild);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.leftChild,root.rightChild);
    }


    /*
    按照先序遍历创建二叉树
     */
    int i = 0;
    public TreeNode creatTree(String str){
        TreeNode root = null;
        if(str.charAt(i)!='#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.leftChild = creatTree(str);
            root.rightChild = creatTree(str);
        }
        else{
            i++;
        }
        return root;
    }

    /*
    实现二叉树的层序遍历
     */
    public void levelOrder2(TreeNode root){
        if (root == null)return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur!=null){
                System.out.print(cur.val+" ");
                queue.offer(cur.leftChild);
                queue.offer(cur.rightChild);
            }
        }
    }

    public List<List<Character>> levelOrder(TreeNode root) {
        List<List<Character>> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Character> list = new ArrayList<>();
            while(size!=0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.leftChild!=null){
                    queue.offer(cur.leftChild);
                }
                if(cur.rightChild!=null){
                    queue.offer(cur.rightChild);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

    /*
    二叉树的最近公共祖先
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p ||root==q){
            return root;
        }
        TreeNode leftT = lowestCommonAncestor(root.leftChild,p,q);
        TreeNode rightT = lowestCommonAncestor(root.rightChild,p,q);
        if(leftT!=null && rightT!=null){
            return root;
        }
        if(leftT!=null){
            return leftT;
        }
        return rightT;
    }

    /*
    公共祖先求法2：最近的路径
     */
    public boolean getPath(TreeNode root, TreeNode p, Stack<TreeNode> stack){
        if(root==null || p==null){
            return false;
        }
        stack.push(root);
        if(root==p)return true;
        boolean flg = getPath(root.leftChild,p,stack);
        if(flg)return true;
        flg = getPath(root.rightChild,p,stack);
        if(flg)return true;
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1>size2){
            int size = size1 - size2;
            while(size!=0){
                stack1.pop();
                size--;
            }
            while(!stack1.isEmpty() && !stack2.isEmpty()){
                if(stack1.peek()==stack2.peek()){
                    return stack1.pop();
                }
                stack1.pop();
                stack2.pop();
            }
        }else{
            int size = size2 - size1;
            while(size!=0){
                stack2.pop();
                size--;
            }
            while(!stack1.isEmpty() && !stack2.isEmpty()){
                if(stack1.peek()==stack2.peek()){
                    return stack1.pop();
                }
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }

    /*
    二叉树最大宽度
    描述：每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
    思路：节点的值无用，可以结合完全二叉树的性质将节点进行编号。
    完全二叉树的一个节点序号为i，其左子节点的序号为2*i+1，其右节点的序号为2*i+2。
    层序遍历（用队列）二叉树，求出每一层的宽度。
     */
//    public int widthOfBinaryTree(TreeNode root) {
//        if(root==null)return 0;
//        LinkedList<TreeNode> queue = new LinkedList<>();//使用链表以调用getFirst()和getLast()方法
//        root.val = 0;
//        queue.add(root);
//        int maxWidth = queue.size();
//        while(!queue.isEmpty()){
//            int size = queue.size();
//            int width = queue.getLast().val-queue.getFirst().val+1;//求出每一层的宽度
//            if(width>maxWidth)maxWidth=width;
//            //遍历下一层
//            while(size!=0){
//                TreeNode cur = queue.poll();
//                if(cur.left!=null){
//                    cur.left.val = cur.val*2+1;
//                    queue.add(cur.left);
//                }
//                if(cur.right!=null){
//                    cur.right.val = cur.val*2+2;
//                    queue.add(cur.right);
//                }
//                size--;
//            }
//        }
//        return maxWidth;
//    }

    /*
    将二叉搜索树转换成一个排序的双向链表
    思路：
    1.中序遍历
    2.left变成前驱 right变成后继
     */
    TreeNode prev = null;
    public void inOrder2(TreeNode root){//中序遍历
        if(root==null)return;
        inOrder(root.leftChild);
        root.leftChild = prev;//left变成前驱
        if(prev!=null){
            prev.rightChild = root;//right变成后继
        }
        prev = root;//记录下当前的位置
        inOrder(root.rightChild);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null)return null;
        inOrder2(pRootOfTree);//转换成一个排序的双向链表
        //返回双向链表的头结点
        while(pRootOfTree.leftChild!=null){
            pRootOfTree=pRootOfTree.leftChild;
        }
        return pRootOfTree;
    }

    /*
    从前序与中序遍历序列构造二叉树
    思路：
    1、首先根据前序遍历找到根
    2、在中序遍历中找到根所在的位置
    3、缩小范围，递归构建子树
     */
//    int pi = 0;
//    public TreeNode buildTreeByPandI(int[] preorder, int[] inorder,int ib, int ie){
//        if(ib>ie)return null;
//        TreeNode root = new TreeNode(preorder[pi]);
//        pi++;
//        int ir = findIndexOfI(inorder,ib,ie,root.val);
//        root.left = buildTreeByPandI(preorder,inorder,ib,ir-1);
//        root.right = buildTreeByPandI(preorder,inorder,ir+1,ie);
//        return root;
//    }
//
//    private int findIndexOfI(int[] inorder,int ib, int ie, int key){
//        for(int i = ib; i <= ie ; i++){
//            if(key == inorder[i])return i;
//        }
//        return -1;
//    }
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        if(preorder==null || inorder==null)return null;
//        return buildTreeByPandI(preorder,inorder,0,inorder.length-1);
//    }


    /*
     从中序与后序遍历序列构造二叉树
     注意区别：
     1、pi从postorder.length-1开始递减
     2、先构建右子树再构建左子树
     */
//    int pi = 0;
//    public TreeNode buildTreeByIandP(int[] postorder, int[] inorder,int ib, int ie){
//        if(ib>ie)return null;
//        TreeNode root = new TreeNode(postorder[pi]);
//        pi--;
//        int ir = findIndexOfI(inorder,ib,ie,root.val);
//        if(ir<0)return null;
//        root.right = buildTreeByIandP(postorder,inorder,ir+1,ie);
//        root.left = buildTreeByIandP(postorder,inorder,ib,ir-1);
//        return root;
//    }
//
//    private int findIndexOfI(int[] inorder,int ib, int ie, int key){
//        for(int i = ib; i <= ie ; i++){
//            if(key == inorder[i])return i;
//        }
//        return -1;
//    }
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        if(postorder==null || inorder==null)return null;
//        pi = postorder.length-1;
//        return buildTreeByIandP(postorder,inorder,0,inorder.length-1);
//    }


    /*
    二叉树创建字符串
     */
    public void treeToStr(TreeNode root, StringBuilder s){
        if(root == null)return;
        s.append(root.val);
        if(root.leftChild!=null){
            s.append("(");
            treeToStr(root.leftChild,s);
            s.append(")");
        }else{
            if(root.rightChild!=null){
                s.append("()");
            }else{
                return;
            }
        }
        if(root.rightChild!=null){
            s.append("(");
            treeToStr(root.rightChild,s);
            s.append(")");
        }else{
            return;
        }
    }
    public String tree2str(TreeNode root) {
        if(root==null)return null;
        StringBuilder str = new StringBuilder();
        treeToStr(root,str);
        return str.toString();
    }

    /*
    递增顺序查找树
     */
    TreeNode pCur = null;
    public void inOrder3(TreeNode root){
        if(root==null)return;
        inOrder3(root.leftChild);
        if(pCur!=null){
            root.leftChild = null;
            pCur.rightChild = root;
        }
        pCur = root;
        inOrder3(root.rightChild);
    }

    public TreeNode increasingBST(TreeNode root) {
        if(root==null)return null;
        TreeNode ret = root;
        while(ret.leftChild!=null){
            ret = ret.leftChild;
        }
        inOrder3(root);
        return ret;
    }

    /*
    非递归实现前序遍历
     */
    public List<Character> preorderTraversal3(TreeNode root) {
        List<Character> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                ret.add(cur.val);
                cur = cur.leftChild;
            }
            TreeNode top = stack.pop();
            cur = top.rightChild;
        }
        return ret;
    }

    /*
    非递归实现中序遍历
     */
    public List<Character> inorderTraversal3(TreeNode root) {
        List<Character> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur = cur.leftChild;
            }
            TreeNode top = stack.pop();
            ret.add(top.val);
            cur = top.rightChild;
        }
        return ret;
    }

    /*
    非递归实现后序遍历
     */
    public List<Character> postorderTraversal3(TreeNode root) {
        List<Character> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null || !stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur = cur.leftChild;
            }
            TreeNode top = stack.peek();
            if(top.rightChild==null || top.rightChild==prev){
                stack.pop();
                ret.add(top.val);
                prev = top;
            }else{
                cur = top.rightChild;
            }
        }
        return ret;
    }


    public static void main(String[] args) {
        TreeNode root2 = new TreeNode('2');
        root2.leftChild = new TreeNode('1');
        TreeNode root4 = new TreeNode('4');
        root2.rightChild = root4;
        root4.leftChild = new TreeNode('3');

        BinaryTree binaryTree = new BinaryTree();
//        TreeNode root = binaryTree.creatTree("abc##de#g##f###");
//        binaryTree.preOrder(root);
//        System.out.println();
//        binaryTree.inOrder(root);
//        System.out.println();
        binaryTree.levelOrder2(root2);
        TreeNode ret = binaryTree.increasingBST(root2);
        System.out.println(ret.val);

    }
}
